package leetcode.problems;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * _0407 Find All Numbers Disappeared in an Array
 * 合并两个有序列表
 * Created by gmwang on 2018/3/23
 */
public class _0407FindAllNumbersDisappearedinanArray {
    /**
     *   Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
         Find all the elements of [1, n] inclusive that do not appear in this array.
         Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
             Example:
             Input:
             [4,3,2,7,8,2,3,1]
             Output:
             [5,6]
        给定整数的数组，查找[1，n ]的所有元素，n是数组长度（有些元素出现超过两次），没出现在这个数组中的元素。
             例：
             输入：
             [4,3,2,7,8,2,3,1]
             输出：
             [5,6]
     */
    /**
     * 思路：
     * 1. 求出一个 (1- n)集合
     * 2. 再求出当前非重复元素集合
     * 3. 取补集
     *
     * @param
     * @return
     */
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> list = new HashSet<>();
        List<Integer> listRes = new ArrayList<>();
        for(int num = 0,length = nums.length;num < length;num++){
            listRes.add(num + 1);
            list.add(nums[num]);
        }
        listRes.removeAll(list);
        return listRes;
   }

    public static void main(String[] args) {
        int[] nums = {4,3,2,7,8,2,3,1};
        System.out.println(findDisappearedNumbers(nums));
    }
}
